# 二叉树前序遍历

class Node():
    def __init__(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

# 创建一颗二叉树
root = Node(23)
root.left = Node(34)
root.right = Node(21)
root.left.left = Node(99)
root.right.left = Node(45)
root.right.right = Node(60)
root.left.left.left = Node(77)
root.left.left.right = Node(90)


class Solution:

    def DLR(self, root: Node) -> list:
        """
            1. 前序遍历： 递归写法
        """
        rst = list()
        def bianli1(node):
            # 递归终止条件
            if not node: return 

            # 1. 中间结点加入进来
            rst.append(node.val)
            # 2. 左右节点加进来
            bianli1(node.left)
            bianli1(node.right)

        # 还可以这样写
        def bianli1(node): 
            # 1. 中间结点加入进来
            rst.append(node.val)
            # 2. 左右节点加进来
            if node.left:
                bianli1(node.left)
            if node.right:
                bianli1(node.right)

        bianli1(root)        
    
        return rst
    
    def DLR1(self, root):
        """
            2. 前序遍历： 显示栈写法
            自定义一个栈
        """
        stack = list()
        stack.append(root)

        rst = []
        while stack:
            curNode = stack.pop()
            # 1. 拿到栈顶节点，值入栈
            rst.append(curNode.val)
            # 2. 左右节点各入栈，先入right ，则left在栈顶，先计算
            if curNode.right: stack.append(curNode.right)
            if curNode.left: stack.append(curNode.left)

        return rst

s = Solution()
rst = s.DLR(root)
print(rst)
